In the field of management and operation of so-called sensitive information, such as customer information and management information, the information to be managed is increasing in variety, and the information processing technology such as cloud computing is changing, so that measures to ensure security and privacy are becoming more important. Recently, the secret sharing art has become popular to prevent leakage of information by distributing the information among plural sites. Besides, a secure functional computation (a multi-party protocol) for deriving a specified computation result without reconstructing the distributed information is also being developed for commercialization. The secret sharing art is effective as a measure to ensure security when storing information but has a risk of leakage of information when using the information, because the information generally needs to be reconstructed for use. In view of the presence of such a risk of leakage of information, the secure functional computation can uses distributed information as operands for computation instead of the original input values and does not need to reconstruct the original input values at all in the computation process. Therefore, the secure functional computation can be said to be an advanced security art that maintains the functionality of the secret sharing art even when the information is used.
A prior art for performing a multiplication while concealing information is a multiplication protocol described in Non-Patent literature 1. A prior art for performing a sum-of-product computation while concealing information is a combination of a multiplication protocol and an addition protocol. These protocols are 3-party secure functional computation protocols that derive a result of an arithmetic/logical operation by cooperative computation by three parties (three computing entities) without reconstructing a shared input value. In the 3-party secure functional computation protocol, data is treated as a natural number smaller than a predetermined prime number p. To conceal data, which will be denoted as “a”, the data a is divided into three fragments in such a manner that the fragments satisfy the following condition.a=a0+a1+a2 mod p In practice, random numbers a0 and a1 are generated, and a relation holds: a2=a−a0−a1. Then, a random number sequence (a0, a1) is transmitted to a party X of the three parties, a random number sequence (a1, a2) is transmitted to a party Y of the three parties, and a random number sequence (a2, a0) is transmitted to a party Z of the three parties. Since a1 and a2 are random numbers, any of the parties X, Y and Z does not have information about the data a. However, any two of the parties can cooperate to reconstruct the data a.
Since the concealment is an additive distribution, the shared value can be equally reconstructed before or after addition of its fragments because of the interchangeability. That is, the addition and the constant multiplication of the distributed fragments can be achieved without communications. If a multiplication can additionally be performed, a logical circuit can be formed, and any computation can be performed. The multiplication needs communications and random number generation and therefore is a bottleneck of the 3-party secure functional computation.